package leetcode;


import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 求组合的所有数据 dfs算法
 * 相当于求集合的所有子集的变形。
 */
public class T77 {

    public List<List<Integer>> combine(int n, int k) {
        int[] integer = new int[n];
        for (int i = 0; i < n; i++) {
            integer[i] = i + 1;
        }
        List<List<Integer>> result = new ArrayList<>();

        subSet(integer, 0, k,new ArrayList<>(),result);

        return result;
    }

    public void subSet(int[] arr, int cur,int rest ,List<Integer> tmp,List<List<Integer>> result) {
        if (rest == 0 ) {
//            System.out.println(tmp);
            result.add(tmp.stream().collect(Collectors.toList()));
            return;
        }
        if(cur >= arr.length){
            return;
        }
        tmp.add(arr[cur]);
        subSet(arr, cur + 1,rest -1,tmp,result);

        tmp.remove(tmp.size() - 1);
        subSet(arr, cur + 1,rest,tmp,result);

    }


    public static void main(String[] args) {
        T77 t77 = new T77();
        List<List<Integer>> combine = t77.combine(5, 3);
        System.out.println(combine);
    }
}
